A goal of three-dimensional (3D) pattern recognition is to recognize objects, such as faces or vehicles, in 3D range imagery. The central problem in 3D pattern recognition is to determine the extent to which one shape differs from another.
For example, facial recognition (FR) is an appealing biometric for many applications because of its non-intrusive nature, ease of integration into existing systems, and potential to identify individuals at a distance without the individual's cooperation. These attributes make the technology ideal for the screening of individuals at borders, airports, secure facilities, etc. Most of the current efforts in FR use a two-dimensional (2D) representation of the face. While much progress has been made over the last decade, 2D FR systems are not generally robust to variations such as facial pose, scene lighting, and facial expression. In addition, the task of positive identification becomes increasingly difficult when confronted with large numbers of people to screen. See R. Chellappa Zhao et al., “Face Recognition: A Literature Survey,” CVL Technical Report, University of Maryland, October 2000; and P. J. Phillips et al., “Face Recognition Vendor Test 2002: Evaluation Report,” http://www.frvt.org/DLs/FRVT—2002_Evaluation_Report.pdf.
To overcome many of the limitations associated with 2D FR technology, researchers are beginning to examine the benefits of 3D data for the FR task. 3D FR systems are expected to be less sensitive to lighting and facial pose variations. In addition, the geometric information available is thought to provide more discriminatory features for facial recognition, including size information which is lacking in most 2D approaches. See K. W. Bowyer et al., “A survey of approaches to 3D and Multi-modal 3D+2D face recognition,” Int. Conf. on Pattern Recognition, August, 2003.
Despite this, many 3D data sets have attributes that present challenges for 3D FR algorithms. For instance, corresponding areas of the face may not always be available over multiple scans due to facial pose variation and object self-occlusion. Also, incorrect or missing data regions may occur due to sensor drop-outs and/or sensor noise characteristics. Variations in datasets acquired of the same individual due to changes in facial expression, hairstyle, glasses, etc. also present a challenge. In many cases, the ability to handle these data issues can be more important than the underlying algorithm used for recognition. For this reason, 3D algorithms must be robust to these types of variations. In addition, the large number of faces in real world databases makes computationally intensive algorithms impractical for scanning entire databases. This is especially true for 3D facial recognition systems, as they tend to use more complex algorithms than the traditional 2D approaches to handle 3D rotation and translation.
One approach to pattern recognition is to use a template from a database of objects and match it to a probe image containing the unknown. Mean square error can determine the goodness of the match. However, this approach fails for an obscured object, or if the probe image has excess clutter. See Besl, P. J., and N. D. McKay, “A Method for Registration of 3-D Shapes,” IEEE Transactions on Pattern Analysis and Machine Intelligence 14(2), 239 (1992).
Alternatively, the Hausdorff distance can be used to measure the similarity of two sets of points. In particular, the Hausdorff can measure the goodness of a match in the presence of occlusion, clutter, and noise. The Hausdorff distance measures the extent to which each point of a template object set lies near some point of a probe image set and vice versa. Thus, the distance can be used to determine the degree of resemblance between two objects that are superimposed on one another. See D. P. Huttenlocher et al., “Comparing Images using the Hausdorff Distance,” IEEE Transactions on Pattern Analysis and Machine Intelligence 15(9), 850 (1993), and D. P. Huttenlocher et al., “View-Based Recognition using an Eigenspace Approximation to the Hausdorff Measure,” IEEE Transactions on Pattern Analysis and Machine Intelligence 21(9), 951 (1999), which are incorporated herein by reference. However, existing 3D algorithms for calculating the Hausdorff are computationally intensive, making them impractical for pattern recognition that requires scanning of large databases.